#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    //freopen("in.txt","r",stdin);
    int N;
    scanf("%d",&N);
    int orgi[N];
    int befo[N];
    for(int i=0;i<N;i++){
        scanf("%d",&orgi[i]);
    }
    for(int i=0;i<N;i++){
        scanf("%d",&befo[i]);
    }
    int idx=0;
    while(befo[idx-1]<=befo[idx]&&idx<N){idx++;}
    bool flag=false;
    for(int i=idx;i<N;i++){
        if(befo[i]!=orgi[i]){
            flag=true;
        }
    }
    if(flag==false){
        printf("Insertion Sort\n");
        sort(befo,befo+idx+1);
        printf("%d",befo[0]);
        for(int i=1;i<N;i++){
            printf(" %d",befo[i]);
        }
    }
    else{
        printf("Merge Sort\n");
        for(int step=2;step/2<=N;step*=2){
            bool tell=false;
            for(int i=0;i<N;i++){
                if(orgi[i]!=befo[i]){
                    tell=true;
                    break;
                }
            }
            for(int i=0;i<=N;i+=step){
                sort(orgi+i,orgi+min(i+step,N));
            }
            if(tell==false)break;
        }
        printf("%d",orgi[0]);
        for(int i=1;i<N;i++){
            printf(" %d",orgi[i]);
        }
    }

}